package com.wfm.leetcode.editor.cn;

import java.util.Arrays;

/**
 * dp[i]表示凑满金额i所需最少硬币个数
 */
public class PThree22零钱兑换{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int coinChange(int[] coins, int amount) {
        // keypoint: dp[i]=dp[i-coins[j]]+1;
        int[] dp = new int[amount+1];
        int max = amount+1;
        Arrays.fill(dp,max);
        dp[0]=0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if(i>=coins[j]){
                    dp[i]=Math.min(dp[i-coins[j]]+1,dp[i]);
                }
            }
        }
        return dp[amount]==max?-1:dp[amount];
    }
}
//leetcode submit region end(Prohibit modification and deletion)
    public static void main(String[] args) { 
        Solution solution = new PThree22零钱兑换().new Solution();
    }
}